#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

class Solution01 {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 使用拓扑排序，判断是否有环
        // 邻接表表示图
        // vector<vector<int>> edges(numCourses);
        // vector<int> enEdges(numCourses, 0); // 表示入度
        // for (auto& v : prerequisites) { 
        //     enEdges[v[0]]++;
        //     edges[v[1]].emplace_back(v[0]);
        // }
        // queue<int> q;
        // for (int i = 0; i < numCourses; i++) {
        //     if (enEdges[i] == 0) 
        //         q.push(i);
        // }
        // while (!q.empty()) {
        //     // 拿出一个元素
        //     int num = q.front();
        //     q.pop();
        //     // 在图中删除该边
        //     for (auto e : edges[num]) {
        //         enEdges[e]--;
        //         if (enEdges[e] == 0) q.push(e);
        //     }
        // }
        // //  判断当前入度是否还有大于0的
        vector<int> enEdges(numCourses, 0);
        unordered_map<int, vector<int>> edges;
        for (auto& v : prerequisites) { 
            enEdges[v[0]]++;
            edges[v[1]].emplace_back(v[0]);
        }      

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (enEdges[i] == 0) 
                q.push(i);
        }        

        while (!q.empty()) {
            // 拿出一个元素
            int num = q.front();
            q.pop();
            // 在图中删除该边
            vector<int>& ve = edges[num];
            for (auto e : ve) {
                enEdges[e]--;
                if (enEdges[e] == 0) q.push(e);
            }
        }

        for (auto e : enEdges) 
            if (e > 0) return false;
        return true;
    }
};

class Solution02 {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> ret;
        // 建表和入度
        vector<vector<int>> edges(numCourses);
        vector<int> in(numCourses, 0);

        // 建表
        for (auto& e : prerequisites) {
            int a = e[0], b = e[1];
            // b -> a
            edges[b].emplace_back(a);
            in[a]++;
        }

        queue<int> q;

        // for (auto e : in) 
        //     if (e == 0)
        //         q.push(e);
        for (int i = 0; i < numCourses; i++)
            if (in[i] == 0)
                q.push(i);
        
        while (!q.empty()) {
            int a = q.front(); q.pop();
            ret.emplace_back(a);

            for (auto e : edges[a]) {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }
        }

        for (auto e : in)
            if (e > 0) return vector<int>();

        return ret;
    }
};

class Solution03 {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, string> edges;
        unordered_map<char, int> in;

        // 需要初始化in
        string str;
        for (auto& w : words) {
            for (auto ch : w) {
                if (!in.count(ch))
                    in[ch] = 0, str += ch;
            }
        }

        int len = words.size();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                // string s = words[i], t = words[j];
                // // 收集信息
                // int index = 0;
                // int n = min(s.size(), t.size());
                // while (index < n && s[index] == t[index])
                //     index++;

                // if (index == t.size() && index < s.size()) {
                //     // if (s[index - 1] == t[index - 1]) return "jkrtw";
                //     return "";
                // }

                // char b = s[index], a = t[index];
                // // b -> a
                // if (!edges.count(b) || edges[b].find(a) == string::npos) {
                //     edges[b] += a;
                //     in[a]++;
                // }
                string s = words[i], t = words[j];
                int n = min(s.size(), t.size());
                int i = 0;
                for (; i < n; i++) {
                    if (s[i] != t[i]) {
                        char b = s[i], a = t[i];
                        // b -> a
                        if (!edges.count(b) ||
                            edges[b].find(a) == string::npos) {
                            edges[b] += a;
                            in[a]++;
                        }
                    break;

                    }
                }

                if (i == t.size() && i < s.size()) {
                    // if (s[index - 1] == t[index - 1]) return "jkrtw";
                    return "";
                }
            }
        }

        queue<char> q;
        for (auto ch : str)
            if (in[ch] == 0)
                q.push(ch);

        string ret;

        while (!q.empty()) {
            char ch = q.front();
            q.pop();
            ret += ch;
            string s = edges[ch];
            for (auto e : s) {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }
        }

        return ret.size() == str.size() ? ret : "";
        return ret;
    }
};

int main() {


    return 0;
}